Hinweis: Dieses Video und dieser Podcast wurden mithilfe von KI erstellt auf Grundlage der ursprünglichen Inhalten sowie den technischen Erkenntnissen des Autors des Blogartikels.

Wenn Sie komplexe Softwareprojekte umsetzen, wie entscheiden Sie, in welcher Form Sie Ihre Daten repräsentieren? Geben Sie einfach Arrays von JavaScript-Objekten vom Typ any weiter, die Sie über API-Aufrufe erhalten? Haben Sie sich schon einmal dabei ertappt, zu viel Code zu schreiben und unnötige CPU-Zyklen für Schleifen zu verschwenden, weil Ihre Daten nicht zu den verwendeten Algorithmen passen?

Unabhängig davon, welche Programmiersprache Sie bevorzugen oder ob Ihr Code in der Cloud oder auf einem mobilen Gerät ausgeführt wird: Früher oder später müssen Sie mit Daten arbeiten. Als Webentwickler senden und empfangen Sie ständig Daten über APIs, häufig in großen Mengen. Diese Daten liegen jedoch oft nicht so vor, dass sie sich gut weiterverarbeiten lassen.

Ungeeignete Datenstrukturen machen Code komplexer und können dadurch Entwicklungs- und Wartungskosten erhöhen. Saubere, übersichtliche und vorhersehbare Datenstrukturen machen die Softwareentwicklung angenehmer und können sogar die Qualität des Endprodukts verbessern.

Dieser Artikel stellt Ihnen einen Werkzeugkasten von Datenstrukturen vor, die in TypeScript zur Verfügung stehen. Bei der Auswahl geeigneter Datenstrukturen konzentrieren wir uns auf drei Hauptziele:

1. Performance: Durch die Wahl der richtigen Struktur können Sie die Komplexität Ihres Codes und die Laufzeit teilweise erheblich reduzieren.

2. Memory Management: Die falsche Datenstruktur kann Speicher und Garbage Collection unnötig belasten, während die richtige Struktur vorhandene Ressourcen effizient nutzt. Darüber hinaus können Datenstrukturen dabei helfen zu steuern, welche Daten langfristig im Speicher verbleiben und wie viel Speicher bestimmte Algorithmen benötigen.

3. Wartbarkeit: Gut gewählte Datenstrukturen erleichtern das Lesen des Codes und die Anpassung an neue Anforderungen. Dadurch sinken die Wartungskosten.

Listing 1

let user_1_first_name = 'Karel'
let user_1_last_name = 'Sanchis'
let user_1_email = '[email protected]'
let user_1_address_street_1 = '12 Roxbury Crossing'
let user_1_address_street_2 = 'PO Box 97501'
let user_1_address_city = 'Otacilio Costa'
let user_1_address_postal_code = '88540-000'
let user_1_address_country = 'Brazil'

let user_2_first_name = 'Tim'
let user_2_last_name = 'Pandey'
let user_2_email = '[email protected]'
let user_2_address_street_1 = '6 Elmside Avenue'
let user_2_address_street_2 = ''
let user_2_address_city = 'Pathum Thani'
let user_2_address_postal_code = '90110'
let user_2_address_country = 'Thailand'

 

Bevor wir in die einzelnen Datenstrukturen eintauchen, betrachten wir einige Codebeispiele, die allgemein als schlechte Praxis gelten. Hoffentlich sind Sie in keinem Projekt auf Code wie in Listing 1 gestoßen – ich habe solchen leider bereits gesehen. Auffällig ist sofort das vollständige Fehlen einer echten Datenstruktur. Die einzige „Struktur“ ergibt sich aus der Namenskonvention der Variablen.

Betrachten wir ein weiteres Beispiel:

function join(a, b) { return a + b }

 

Was macht dieser Code? Die Antwort hängt von den übergebenen Datentypen ab. join(1, 2) führt eine Addition aus und liefert 3, während join(‘a’, ‘b’) eine Verkettung durchführt und ‘ab’ zurückgibt. Um die tatsächliche Funktion zu verstehen, müssten wir jede einzelne Stelle im Code untersuchen, an der diese Funktion aufgerufen wird.

Wie lösen wir dieses Problem? – Durch Typisierung:

// Concatenation
function join(a: string, b: string): string {
  return a + b
}

// Addition
function join(a: number, b: number): number {
  return a + b
}

 

Durch die einfache Ergänzung von Typen können wir die beiden Funktionen eindeutig voneinander unterscheiden. Das Beispiel ist zwar etwas konstruiert, verdeutlicht aber sehr klar den Nutzen einer Typisierung für die Verständlichkeit von Code.

Natürlich funktioniert das nur, solange niemand versucht, die Typisierung zu umgehen:

join('x' as any, 3)

 

In TypeScript kann immer jemand Typen so casten, dass Probleme entstehen. Das ist jedoch nicht unbedingt unser Problem, wir sollten lediglich vermeiden, solche Probleme selbst zu verursachen. Im weiteren Verlauf dieses Artikels verzichten wir deshalb auf any und verwenden stattdessen eine saubere Typisierung unserer Datenstrukturen. Richtig eingesetzt macht Typisierung den Code lesbarer und reduziert Fehler.

Jetzt ist es Zeit, sich die Datenstrukturen selbst anzusehen.

Klassifizierung

Es gibt zahlreiche Möglichkeiten, Datenstrukturen zu klassifizieren. Für diesen Artikel verwenden wir jedoch die Einteilung in Abbildung 1.

Wir konzentrieren uns auf nichtprimitive Datenstrukturen. Dabei ist wichtig zu verstehen, dass jede nichtprimitive Datenstruktur letztlich aus Mengen primitiver Datentypen besteht, was sich auch in der Typisierung widerspiegelt. Zur Erläuterung des Diagramms:

• Linear bedeutet eine flache, eindimensionale Struktur.

• Non-Linear bedeutet, dass die Struktur beliebige Konfigurationen annehmen kann.

• Static bedeutet, dass Speicher einmalig reserviert wird und die Größe fest vorgegeben ist.

• Dynamic bedeutet, dass Speicher während der gesamten Lebensdauer der Datenstruktur nach Bedarf hinzugefügt werden kann. Nichtlineare Strukturen sind typischerweise ebenfalls dynamisch.

• Concrete bezeichnet einen Datentyp, der direkt von der Programmiersprache bereitgestellt wird.

• Abstract steht hier für eine Datenstruktur, die wir selbst definieren.

Struct/Record (Non-Linear, Static, Concrete)

Der Typ Struct (beziehungsweise Record) gehört zu den grundlegendsten Datentypen der Programmierung. Die meisten Entwickler verwenden ihn regelmäßig, ohne weiter darüber nachzudenken. Vereinfacht gesagt stellt ein Struct eine Sammlung von Feldern und deren zugehörigen Datentypen dar. Er eignet sich hervorragend zur Organisation von Informationen, beispielsweise:

• ein Benutzer mit Name, E-Mail-Adresse und Telefonnummer

• ein Produkt mit Name, Preis und Abmessungen

Das wäre eine deutlich bessere Alternative zu unserem ursprünglichen Beispiel (Listing 1) mit den beiden Benutzern. In TypeScript lässt sich das mit einem Type-Alias und einem Objekt als Record darstellen (Listing 2).

Listing 2

type UserInfo = {
  name: {
    first: string
    last: string
  }
  email: string
  address: {
    street1: string
    street2?: string
    city: string
    postalCode: string
    country: string
  }
}

const user1: UserInfo = {
  name: { first: 'Karel', last: 'Sanchis' },
  email: '[email protected]',
  address: {
    street1: '12 Roxbury Crossing',
    street2: 'PO Box 97501',
    city: 'Otacilio Costa',
    postalCode: '88540-000',
    country: 'Brazil',
  }
}

const user2: UserInfo = {
  name: { first: 'Tim', last: 'Pandey' },
  email: '[email protected]',
  address: {
    street1: '6 Elmside Avenue',
    city: 'Pathum Thani',
    postalCode: '90110',
    country: 'Thailand',
  }
}

 

Diese Darstellung entspricht vermutlich eher dem, was Sie aus modernen Anwendungen kennen. Gegenüber dem ursprünglichen Beispiel bietet sie mehrere Vorteile:

• Eine einzige Variable enthält sämtliche Daten und kann als einzelner Parameter an Funktionen übergeben werden.

• Durch Typisierung und Struktur ist sichergestellt, dass alle UserInfo-Records dieselbe Form besitzen.

• Der Code wird deutlich verständlicher und leichter wartbar.

Im Kern sind alle TypeScript-Objekte Records, da sie typisierte Felder enthalten. Nach einer strengen Definition gelten JavaScript-Objekte dagegen möglicherweise nicht als Records, da ihnen die Typisierung fehlt.

Über diese einfache Definition hinaus stellt TypeScript sogar einen eigenen Record-Typ bereit, bei dem sowohl der Schlüssel- als auch der Wertetyp definiert werden kann (Listing 3). Dabei wird angenommen, dass:

• alle Schlüssel denselben Typ besitzen

• alle Werte denselben Typ besitzen

Listing 3

type CatName = "miffy" | "boris" | "mordred"
interface CatInfo {
  age: number
  breed: string
}

const cats: Record<CatName, CatInfo> = {
  miffy:   { age: 10, breed: "Persian" },
  boris:   { age: 5,  breed: "Maine Coon" },
  mordred: { age: 16, breed: "British Shorthair" },
}

 

Generics

Dieses Beispiel führt gleichzeitig ein weiteres wichtiges Konzept ein: Generics. Generics ermöglichen es, eine Datenstruktur eines bestimmten Typs zu definieren, die Daten eines anderen Typs enthält. Im Beispiel in Listing 3 ist der eigentliche Typ Record. Die beiden generischen Parameter legen jedoch fest, dass die Schlüssel vom Typ CatName und die Werte vom Typ CatInfo sind.

Denken wir in Listing 4 beispielsweise an geometrische Formen und deren Umrandungen.

Listing 4

type Square = {
  width: number
  height: number
}

type Circle = {
  radius: number
}

type Border<T> = {
  weight: 'light' | 'normal' | 'bold'
  color: string
  shape: T
}

 

Das Generic <T> im Typ Border bedeutet, dass wir Rahmen für beliebige Objekte beschreiben können. Man könnte das weiter einschränken, beispielsweise mit T extends Shape. Dadurch wären nur Unterklassen eines bestimmten Shape-Typs zulässig. Ein konkretes Objekt könnte dann aussehen wie in Listing 5.

Listing 5

let b: Border<Square> = {
  weight: 'bold',
  color: '#000000',
  shape: {
    width: 24,
    height: 36
  }
}

 

Beachten Sie, dass der konkrete Typ des Generic beim Erzeugen des Objekts angegeben wird. Dadurch kann TypeScript überprüfen, ob die übergebenen Werte tatsächlich zur Typdefinition passen. Alle folgenden Datenstrukturen bauen auf diesem Konzept auf.

Array (Linear, Static, Concrete)

Die nächste Datenstruktur dürfte den meisten Entwicklern vertraut sein, da sie in nahezu allen Programmiersprachen zu den Grundtypen gehört. Arrays sind: Linear, Static und Concrete.

Die Elemente eines Arrays erhalten einen Index von 0 bis n – 1, wobei n die Anzahl der Elemente darstellt. (Verwechseln Sie Arrays nicht mit Tupeln, die später im Artikel behandelt werden.) Arrays können enthalten:

• primitive Datentypen wie string oder number

• komplexe Datentypen wie Records

• andere Arrays

Arrays können homogen sein, also ausschließlich Werte desselben Typs enthalten. Sie können aber auch unterschiedliche Datentypen kombinieren. Ein Beispiel sehen Sie in Abbildung 2. Darin enthält das Array fünf Elemente (n = 5) mit unterschiedlichen Datentypen. In TypeScript würde das als any[] beschrieben. Alternativ können Sie Arrays auf bestimmte Typen beschränken, etwa string[] oder Border[].

Wie die grafische Darstellung bereits vermuten lässt, sind die Array-Elemente sequenziell angeordnet. Darüber hinaus sind sie iterierbar, was bedeutet, dass sich ihre Inhalte leicht durchlaufen lassen. Diese Eigenschaft ist für viele Algorithmen von zentraler Bedeutung.

Standardmäßig sind Arrays eindimensional (Abb. 3). Da Arrays jedoch wiederum andere Arrays enthalten können, lassen sich daraus mehrdimensionale Strukturen erzeugen. Zum Beispiel:

• zweidimensionale Arrays als Raster oder Matrizen (Abb. 4)

• dreidimensionale Arrays als Würfel (Abb. 5)

• beliebig viele weitere Dimensionen; Grenzen setzen hier nur der verfügbare Speicher und die Verständlichkeit der Struktur

In TypeScript können Arrays auf unterschiedliche Weise erstellt werden (Listing 6).

Listing 6

let array: string[] = ['a', 'b', 'c']
let complexArray: Array<String | Number> =
  ['a', 2, 'x', 2.3]
let array2d =
  [['x','o','x'],['x','x','o'],['o','o','x']]
let list: number[] = []

list.push(3.14) // Add items to the array

 

Memory Management bei Arrays

Es überrascht kaum, dass Arrays verändert werden können. Allerdings geschieht dies möglicherweise anders, als Sie erwarten.

Betrachten wir die Methode .push(), die ein einzelnes Zeichen zu einem Array hinzufügt (Abb. 6). Dabei wird das neue Element nicht einfach an das bestehende Array angehängt. Stattdessen entsteht intern ein neues Array, während das alte freigegeben wird (Abb. 7).

Die meisten Programmiersprachen verwenden zwar Verfahren wie Predictive Allocation und Compileroptimierungen, um unnötige Speicherbewegungen zu vermeiden. Dennoch sollten Sie verstehen, dass das Hinzufügen eines Elements zu einem Array letztlich bedeutet, dass das Array irgendwann an eine neue Speicheradresse verschoben und der alte Speicher freigegeben werden muss – selbst wenn nur ein einziges Element ergänzt wird.

Arrays lassen sich außerdem zusammenführen. Dafür kann beispielsweise concat verwendet werden (Abb. 8). Das Ergebnis ist erneut ein vollständig neues Array. Die ursprünglichen Arrays bleiben jedoch erhalten (Abb. 9). Sie existieren weiter, bis sie von der Garbage Collection entfernt werden.

Die zwei wichtigsten Erkenntnisse zum Memory-Management von Arrays sind:

1. Viele Änderungen an einem Array können zahlreiche Speicheroperationen verursachen.

2. Das Durchlaufen eines Arrays ist sehr schnell, da die Speicherbereiche sequenziell angeordnet sind.

Iteration

Wie bereits erwähnt, sind Arrays iterierbar. Doch was bedeutet das konkret? In TypeScript gibt es vier grundlegende Möglichkeiten, über ein Array zu iterieren beziehungsweise es in Schleifen zu durchlaufen (Listing 7).

Listing 7

// for loop
for (let i = 0; i < a.length; i++) {
  console.log(a[i])
}

// for-in
for (const elem in a) {
  console.log(elem)
}

// for-of
for (const elem of a) {
  console.log(elem)
}

// forEach
a.forEach(elem => {
  console.log(elem)
})

 

Die klassische for-Schleife ist ein bewährter Standard. Sie funktioniert zuverlässig, drückt die Absicht aber weniger klar aus als for-of und ist weniger flexibel kombinierbar als forEach. Dafür lässt sie sich leicht mit async/await synchronisieren.

Eine Warnung: Die for-in-Schleife verwendet ausdrücklich nicht den eingebauten Array-Iterator. Stattdessen iteriert sie über sämtliche Schlüssel des Array-Objekts. Das bedeutet, dass auch Eigenschaften, die keine eigentlichen Arrayelemente sind (beispielsweise length), in die Iteration einbezogen werden können. In den meisten Fällen ist das nicht das gewünschte Verhalten, kann in bestimmten Situationen jedoch nützlich sein.

Array-Transformationen mit every, some, filter und map

Es gibt außerdem Methoden, die auf der Iterierbarkeit von Arrays aufbauen, ohne selbst klassische Iteratoren zu sein (Listing 8).

Listing 8

const a = [1, 32, 7, 16, 9, 11]
a.every(elem => elem > 0)       // true
a.some(elem => elem > 30)       // true
a.filter(elem => elem % 2 == 0) // [32, 16]
a.map((n, i) => ({
  i,
  n,
  even: n % 2 == 0
}))

// Ergebnis von map:
[
  { i:0, n:1, even:false },
  { i:1, n:32, even:true },
  ...
]

 

Die einzelnen Methoden erfüllen unterschiedliche Aufgaben:

• every: Prüft, ob jedes Element eine bestimmte Bedingung erfüllt.

• some: Prüft, ob mindestens ein Element die Bedingung erfüllt.

• filter: Entfernt alle Elemente, die eine Bedingung nicht erfüllen.

• map: Verändert die Struktur jedes Elements. Dabei kann sogar ein vollständig anderer Datentyp erzeugt werden.

Wenn Sie mit Datenstrukturen arbeiten, ist es wichtig zu verstehen, wie sich Daten zwischen unterschiedlichen Typen umwandeln lassen. Genau dafür sind solche Methoden besonders wertvoll.

Reduce

Eine weitere wichtige Methode zur Datenumwandlung ist reduce. Während map einzelne Elemente verändert, erlaubt reduce, Form und Typ des Ergebnisses vollständig neu zu definieren (Listing 9).

Listing 9

const employees = [
  { id:23, name:'Frank' },
  { id:73, name:'Sally' }
]
const byId = employees.reduce((acc, emp) => {
  acc[emp.id] = emp
  return acc
}, {})

 

Danach kann folgendermaßen auf die Daten zugegriffen werden:

byId[23].name === 'Frank'

 

anstelle von:

employees.find(emp => emp.id == 23)?.name === 'Frank'

 

reduce ist äußerst leistungsfähig und flexibel. Ein häufiger Anwendungsfall besteht darin, ein Array von Werten in eine Lookup-Struktur umzuwandeln.

Im Beispiel wird einmalig eine Operation mit der Komplexität O(n) ausgeführt. Anschließend erfolgen alle weiteren Suchen nach einer ID mit einer Komplexität von O(1). Wenn lediglich ein einzelner Mitarbeiter gesucht werden soll, lohnt sich dieser Aufwand möglicherweise nicht. Aber bereits bei der zweiten oder dritten Suche kann sich der Performancegewinn deutlich auszahlen.

Tupel (Linear, Static, Abstract)

Ein Tupel ist eine geordnete und endliche Liste von Elementen, die auf den ersten Blick einem Array ähnelt. Im Unterschied zu einem Array, das üblicherweise als [1, 2, 3] notiert wird, wird ein Tupel in der theoretischen Beschreibung häufig als (1, 2, 3) dargestellt. Ein Tupel wird durch folgende Eigenschaften definiert:

• Die Länge ist Teil des Typs: Ein Tupel mit drei Einträgen unterscheidet sich grundsätzlich von einem Tupel mit vier Einträgen.

• Die Reihenfolge ist relevant: (1, 2, 3) ≠ (2, 1, 3)

• Tupel sind unveränderlich: Nach ihrer Erstellung dürfen sie nicht mehr verändert werden, um die Datenintegrität zu gewährleisten.

Kurze Tupel besitzen teilweise eigene Bezeichnungen, das sind „Monad“ mit einem einzelnen Wert als Inhalt (Beispiel: (13)) sowie „Pair“ mit zwei Werten (Beispiel: (6, 7)).

Ein Tupel kann wiederholte Typen enthalten (‘pi’, 3.14, ‘e’, 2.718) oder unterschiedliche Typen kombinieren (64738, ‘John Doe’, false). Dadurch eignen sich Tupel sowohl zur Darstellung strukturierter Daten als auch zur Repräsentation von Listen.

In TypeScript werden Tupel mit Hilfe von Arrays erzeugt. Die Beispiele in Listing 10 sind streng genommen noch keine echten Tupel, da sie nicht readonly sind.

Listing 10

const response = [404, 'Not Found']
const tuple: [string, number, string, number] = [
  'pi',
  3.14,
  'e',
  2.718
]
type Phone = [number, number, number, string?]

const phones: Phone[] = [
  [213, 213, 1242],
  [222, 555, 1259, 'x123'],
]

 

Für eine bessere Absicherung können Sie beispielsweise Folgendes verwenden:

const response: readonly [number, string] =
  [404, 'Not Found']

 

oder

const response: [number, string] =
  [404, 'Not Found'] as const

 

Diese Varianten verhindern Fehler bereits während der Kompilierung. Allerdings entsteht dadurch noch kein wirklich unveränderliches Objekt zur Laufzeit, da die zugrunde liegenden JavaScript-Arrays keine entsprechende Garantie bieten.

Set (Linear, Static, Concrete)

Eine weitere eingebaute Collection in TypeScript ist das Set. Ähnlich wie ein Array enthält ein Set eine Sammlung von Werten und ist ebenfalls iterierbar. Sein Einsatzzweck unterscheidet sich jedoch deutlich.

Eine der wichtigsten Eigenschaften eines Sets ist, dass doppelte Einträge automatisch verhindert werden. Ein Set enthält daher ausschließlich eindeutige Werte. Dadurch eignet es sich hervorragend zum Entfernen von Duplikaten:

const s1 = new Set([1, 2, 2, 3])
const a = [...s1]

console.log(JSON.stringify(a))
// Ausgabe: 1, 2, 3

 

Die Umwandlung zwischen Array und Set ist also unkompliziert und ermöglicht einen einfachen Datenaustausch zwischen beiden Strukturen. Darüber hinaus bildet das Set das mathematische Konzept der Mengenlehre nach und unterstützt wichtige Mengenoperationen (Abb. 10). Ein Beispiel sehen Sie in Listing 11.

Listing 11

const fibonacci: Set<number> =
  new Set([0, 1, 1, 2, 3, 5, 8, 13, 21])
const prime: Set<number> =
  new Set([2, 3, 5, 7, 11, 13, 17, 19])

fib.difference(prime)     // 0, 1, 8, 21
fib.intersection(prime)   // 2, 3, 5, 13
fib.union(prime)          // 0, 1, 2, 3, 5, 8, 13, 21, 7, 11, 17, 19

 

Set ist daher eine ausgezeichnete Wahl, wenn

• eindeutige Listen benötigt werden.

• Mengenoperationen durchgeführt werden sollen.

Beachten Sie jedoch, dass Set zur Gleichheitsprüfung das Verfahren SameValueZero verwendet. Für primitive Datentypen funktioniert das hervorragend, bei Objekten wird jedoch nur die Identität geprüft:

• dieselbe Instanz → gleich

• gleiche Inhalte, aber unterschiedliche Instanzen → ungleich

Map (Linear, Dynamic, Concrete)

TypeScript beziehungsweise JavaScript stellt noch eine weitere eingebaute Datenstruktur bereit, die überraschend häufig übersehen wird: die Map. Eine Map ist ein Key-Value-Speicher, ähnlich einem Objekt oder Record, bietet jedoch einige wichtige Eigenschaften, die sie in bestimmten Situationen zur besseren Wahl machen können. Ein Beispiel sehen Sie in Listing 12. Die Eigenschaften einer Map:

• Keine Standardschlüssel oder eingebauten Attribute: Beim Iterieren über die Schlüssel erhalten Sie ausschließlich die Daten, die tatsächlich in der Struktur gespeichert wurden.

• Beibehaltung der Einfügereihenfolge: Die Reihenfolge, in der Einträge hinzugefügt werden, bleibt erhalten. Dadurch vereint die Map Eigenschaften eines Arrays und eines Objekts:

  • Reihenfolge bleibt nachvollziehbar
  • direkter Zugriff auf Einträge ist möglich

• Kein JavaScript-Prototyp: Eine Map besitzt keinen JavaScript-Prototyp und ist dadurch weniger anfällig für unerwünschte Seiteneffekte oder unbeabsichtigte Mutationen.

• Schlüssel können beliebige Typen besitzen: Wie bei einem TypeScript Record können Schlüssel beliebige Typen haben und sind nicht auf String oder Symbol beschränkt.

• Iterierbarkeit und Größenverwaltung: Ähnlich wie Arrays sind Maps iterierbar und ihre Größe wird erfasst.

Listing 12

const contacts = new Map()
contacts.set(
  'Karel',
  '[email protected]'
)
contacts.set(
  'Tim',
  '[email protected]'
)
contacts.size // 2
contacts.get('Tim')
// [email protected]
contacts.forEach(contact => {
  console.log(contact)
})

 

Obwohl eine Map technisch vieles leisten kann, was auch ein Objektliteral kann, ist sie etwas aufwendiger in der Verwendung. Ihren größten Nutzen entfaltet sie dort, wo ihre speziellen Eigenschaften tatsächlich benötigt werden.

List (Linear, Dynamic, Abstract)

Die Liste ist ein abstrakter Datentyp, der eine sequenzielle Sammlung von Daten definiert. Typische Operationen sind:

• Einfügen am Anfang der Liste

• Anhängen am Ende der Liste

• Ermitteln der Listengröße

• Zugriff auf Elemente anhand ihrer Position

• Iteration über die enthaltenen Daten

Möglicherweise fällt Ihnen auf, dass ein Array diese Definition bereits erfüllt. Tatsächlich ist ein Array eine konkrete Implementierung einer Liste. Wenn Sie sich jedoch an die Speichercharakteristika von Arrays erinnern, wird deutlich, dass es Situationen gibt, in denen andere Implementierungen sinnvoller sind.

Linked List (Linear, Dynamic, Concrete)

Eine Linked List besteht aus einer Folge von Records (oder Pairs), die jeweils aus zwei Teilen bestehen:

• dem eigentlichen Datenelement

• einer Referenz auf das nächste Element

Jeder dieser Records wird als Node bezeichnet (Abb. 11). Beim Zugriff auf ein Element anhand seines Index wird Node für Node durchlaufen, während die besuchten Elemente gezählt werden. Zum Hinzufügen eines neuen Elements wird der letzte Node der Liste gesucht und auf den neuen Node verwiesen.

Eine einfache TypeScript-Implementierung könnte aussehen wie in Listing 13.

Listing 13

type Node<T> = {
  val: T,
  next: Node<T>
}
class LinkedList<T> {
  size = 0
  first: Node<T>
  add(val: T) {
    const node = { val, next: null }
    if (!this.first) {
      this.first = node
    } else {
      let x = this.first
      while (x.next != null) {
        x = x.next
      }
      x.next = node
    }
    this.size++
  }
  get(n: number): T {
    let node = this.first
    for (let i = 0; i < n; i++) {
      node = node?.next
    }
    return node?.val
  }
}

 

Neben dem Einfügen der Daten verwaltet die Methode add auch einen Zähler für die Listengröße. Das wäre nicht zwingend erforderlich, da die Nodes jederzeit gezählt werden könnten. Durch die gespeicherte Größe wird das Auslesen der Listenlänge jedoch zu einer sehr günstigen Operation. Die Verwendung dieser Implementierung sieht folgendermaßen aus:

const list = new LinkedList<string>()
list.add('Karel')
list.add('Tim')
list.add('Sally')

console.log(list.get(1))
// Tim

 

Dank der generischen Typdefinition kann die Liste beliebige Datentypen aufnehmen.

Linked Lists besitzen einige Vorteile. Sie sind häufig:

• schneller beim schrittweisen Hinzufügen einzelner Elemente

• speichereffizienter bei dynamischen Erweiterungen

Arrays sind dagegen meist:

• schneller beim Lesen von Daten

• effizienter bei häufigem Direktzugriff

Listen können außerdem vorwärts und rückwärts verlinkt werden, wodurch bestimmte Operationen günstiger werden.

Stack (Linear, Dynamic, Abstract)

Der Stack (Abb. 12) ist eine ausgesprochen anschauliche Datenstruktur. Man kann ihn sich wie einen physischen Stapel Papier vorstellen. Auf einen Stapel können Sie:

• oben etwas ablegen

• oben etwas entfernen

• oben nachsehen, welches Element sich aktuell dort befindet

Daraus ergeben sich die grundlegenden Operationen:

• push

• pop

• peek

Wie bei der Liste kann ein Stack einfach mit einem Array implementiert werden. TypeScript-Arrays besitzen bereits die Methoden push() und pop(). Da diese Methoden das Ende des Arrays verändern, kann peek() einfach über folgenden Zugriff realisiert werden: stack[stack.length – 1].

Die zulässigen Operationen definieren einen Stack als FILO (First In, Last Out), das bedeutet: Sobald sich ein Element am Boden des Stapels befindet, müssen zunächst alle darüberliegenden Elemente entfernt werden, bevor darauf zugegriffen werden kann.

Linked Stack (Linear, Dynamic, Concrete)

Obwohl Arrays für Stacks häufig ausreichen, gibt es Situationen, in denen eine eigene Implementierung sinnvoll ist. Im Gegensatz zur Liste ist ein Linked Stack (Listing 14) bei allen Operationen mindestens ebenso effizient und bietet zugleich sehr gutes Memory Management.

Listing 14

type Node<T> = {
  val: T,
  next: Node<T>
}

class Stack<T> {
  top: Node<T>

  push(val: T) {
    this.top = {
      val,
      next: this.top
    }
  }

  pop(): T {
    const node = this.top
    this.top = node?.next
    return node?.val
  }

  peek(): T {
    return this.top?.val
  }
}

 

Möglicherweise fällt Ihnen in Listing 14 auf, dass jeder Node zwei Variablen enthält. Dadurch kann ein Linked Stack theoretisch doppelt so viel Speicher benötigen wie ein Array. In der Praxis spielt das jedoch hauptsächlich dann eine Rolle, wenn die Daten statisch sind und der reservierte Speicher exakt dem Bedarf entspricht. Ein Beispiel zur Verwendung sehen Sie in Listing 15.

Listing 15

const stack = new Stack<string>()

stack.push('Mark')
stack.push('Mary')

console.log(stack.peek())
// Mary

stack.pop() === 'Mary'

console.log(stack.peek())
// Mark

 

Stacks eignen sich besonders für hochdynamische Szenarien, in denen Elemente schnell hinzugefügt und entfernt werden müssen. In dieser Implementierung besteht:

• push aus einer einzigen Zuweisung

• pop aus lediglich zwei Zuweisungen

Queue (Linear, Dynamic, Abstract)

Mein persönlicher Lieblingsaspekt der Queue ist ihre ausgesprochen treffende Bezeichnung. Im Englischen besteht das Wort „Queue“ praktisch aus einem einzigen hörbaren Buchstaben (Q) und einer Reihe stiller Buchstaben, die geduldig anstehen. Genau so funktioniert die Datenstruktur. Die Queue ist eine FIFO-Struktur (First In, First Out) und bildet damit das Gegenstück zum FILO-Prinzip eines Stacks. Die wichtigsten Operationen (Abb. 13) sind:

• enqueue() – Element hinzufügen

• dequeue() – Element entfernen und zurückgeben

Das Verhalten einer Queue lässt sich mit einem Array nachbilden:

const queue: string[] = []

queue.push('Mark') // enqueue
queue.push('Mary') // enqueue

queue.shift() === 'Mark'
// dequeue

 

Für Queues mit relativ stabiler Größe funktioniert diese Implementierung oft sehr gut. In manchen Anwendungen schwankt die Anzahl der Elemente jedoch stark. Dann kann eine eigene Implementierung mit vorhersehbarer Performance sinnvoller sein.

Linked Queue (Linear, Dynamic, Concrete)

Die Linked Queue ähnelt den bereits vorgestellten Implementierungen von List und Stack. Der Unterschied besteht darin, dass beide Enden der Struktur verfolgt werden:

• Anfang (top)

• Ende (end)

Dadurch können Elemente effizient an einem Ende eingefügt und am anderen Ende entfernt werden. Die Einfüge- und Löschlogik wird etwas komplexer, dafür entfällt jeglicher Aufwand zum Auffinden von Anfang oder Ende (Listing 16).

Listing 16

type Node<T> = {
  val: T,
  next: Node<T>
}

class Queue<T> {
  private top: Node<T>
  private end: Node<T>
  size = 0

  enqueue(val: T) {
    const node = {
      val,
      next: null
    }
    if (!this.end) {
      this.top = node
    } else {
      this.end.next = node
    }
    this.end = node
    this.size++
  }

  dequeue(): T {
    const node = this.top
    this.top = node?.next
    if (!this.top) {
      this.end = null
    }
    this.size--
    return node?.val
  }
}

 

Queues begegnen uns überall, z. B. bei Ampelanlagen, Supermarktkassen, Druckerwarteschlangen. In der Softwareentwicklung bilden sie die Grundlage nahezu jeder Pipeline, einschließlich Messaging-Systemen und Message Brokern.

Tree (Non-Linear, Dynamic, Abstract)

Die erste nichtlineare Datenstruktur, die wir betrachten, ist der Baum (Tree). Ironischerweise wird ein Tree in Darstellungen meist breiter an der Basis als an der Spitze gezeichnet und ähnelt damit eher einer Pyramide. Tatsächlich ist seine Struktur jedoch eher mit einem Stammbaum oder einem Organigramm vergleichbar (Abb. 14).

Die Beziehungen zwischen den Elementen werden ähnlich wie in einem Familienstammbaum mit familiären Begriffen beschrieben: Parent, Child, Siblings, Ancestors. Alle diese Bezeichnungen sind gültig. Jeder Eintrag im Tree wird üblicherweise als Node bezeichnet. Endknoten ohne Nachkommen werden häufig Leaves genannt.

Ein wichtiger Aspekt von Trees ist außerdem, dass jeder einzelne Node, für sich betrachtet, wiederum einen eigenen Teilbaum (Subtree) darstellt. Genau darauf basiert die Navigation innerhalb eines Trees: Mit Hilfe von Rekursion kann jeder gültige Subtree separat verarbeitet werden.

Ein besonders wichtiger Bestandteil der Definition eines Trees ist, dass seine Struktur immer von oben nach unten verläuft. Dabei gelten zwei Regeln:

1. Nodes dürfen ausschließlich über Parent-Child-Beziehungen verbunden sein.

2. Jeder Node darf genau einen Parent besitzen.

Der Ausgangspunkt für eine einfache Tree-Implementierung in TypeScript ähnelt den zuvor vorgestellten Datenstrukturen (Listing 17).

Listing 17

class TreeNode<T> {
  private data: T
  private children: TreeNode<T>[]

  constructor(data: T) {
    this.data = data
    this.children = []
  }

  addChild(child: TreeNode<T>): void {
    this.children.push(child)
  }

  getData(): T {
    return this.data
  }

  getChildren(): TreeNode<T>[] {
    return this.children
  }
}

 

Jeder beliebige TreeNode ist selbst bereits ein vollständiger Tree, der keinen, einen oder beliebig viele Kindknoten enthalten kann. Deshalb ergibt bereits folgende Anweisung einen gültigen Tree:

const tree = new TreeNode('Hello, World!')

 

Trees bilden die Grundlage zahlreicher Algorithmen und Systeme, darunter:

• Routingalgorithmen

• Heap Sort

• Game Trees

• Decision Trees

• viele weitere Anwendungen

Es existiert eine große Zahl spezialisierter Tree-Varianten für unterschiedliche Anforderungen.

Heap

Beim Heap gilt:

• Bei einem Max-Heap ist jeder Parent größer oder gleich seinen Children.

• Bei einem Min-Heap ist jeder Parent kleiner oder gleich seinen Children.

Binary Tree

Beim Binary Tree darf jeder Parent höchstens zwei Children besitzen. Binary Trees werden häufig für Suchalgorithmen eingesetzt, während Heaps typischerweise beim Sortieren verwendet werden. Beide besitzen darüber hinaus zahlreiche weitere Anwendungsgebiete.

Graph (Non-Linear, Dynamic, Abstract)

Die letzte Datenstruktur dieses Artikels ist der Graph (Abb. 15). In vieler Hinsicht ähnelt ein Graph einem Tree. Der entscheidende Unterschied ist, dass ein Graph auf sich selbst zurückverweisen darf. Dadurch können Schleifen und zyklische Verbindungen entstehen.

Die Terminologie unterscheidet sich etwas von der eines Trees:

• Ein Graph besteht aus Edges (manchmal auch Paths genannt)

• sowie Vertices (ein Vertex entspricht einem Node)

Die offensichtlichste Anwendung eines Graphen ist die Kartennavigation:

• Straßen entsprechen den Edges

• Kreuzungen entsprechen den Vertices

Weitere Einsatzgebiete sind:

• Social Graphs

• Modellierung von Beziehungen

• Chemie

• Supply-Chain-Management

• Netzwerkplanung

• viele weitere Bereiche

Der Graph ist vermutlich die komplexeste und zugleich wichtigste Datenstruktur in diesem Artikel. Über Graphen wurden ganze Bücher geschrieben und trotzdem lässt sich auch ein einfacher Graph in TypeScript erstellen (Listing 18).

Listing 18

class GraphNode<T> {
  private data: T
  private neighbors: GraphNode<T>[]
  constructor(data: T) {
    this.data = data
    this.neighbors = []
  }
  addNeighbor(child: GraphNode<T>): void {
    this.neighbors.push(child)
  }
}

class Graph<T> {
  nodes: GraphNode<T>[] = []

  addNode(value: T) {
    const node = new GraphNode<T>(value)
    this.nodes.push(node)
  }

  addEdge(
    source: GraphNode<T>,
    destination: GraphNode<T>
  ) {
    source.addNeighbor(destination)
    destination.addNeighbor(source)
  }
}

 

Für die Konsistenz mit den übrigen Beispielen wurde hier die Bezeichnung GraphNode verwendet. Ebenso gut könnte dieser Typ auch Vertex heißen. Beachten Sie außerdem, dass diese Implementierung Nodes ohne Edges zulässt. Dadurch entstehen isolierte Nodes, die nicht erreichbar oder navigierbar sind. Das ist nicht zwangsläufig falsch, kann aber in bestimmten Situationen Probleme verursachen.

Ein weiterer wichtiger Punkt: Bei Graphen können rekursive Traversierungen sehr leicht zu Endlosschleifen führen. Anders als bei Trees reicht eine einfache rekursive Navigation oft nicht aus.

Für den effizienten Umgang mit Graphdaten sollten Sie etablierte Traversierungs- und Pathfinding-Algorithmen verwenden, beispielsweise:

• BFS (Breadth-first Search)

• DFS (Depth-first Search)

• Dijkstra-Algorithmus

• Bellman-Ford-Algorithmus

Fazit

In diesem Artikel haben wir zehn unterschiedliche Datenstrukturen betrachtet, von naheliegenden bis hin zu weniger bekannten. Wir haben dabei ein allgemeines Klassifikationssystem eingeführt, das Ihnen bei der Auswahl geeigneter Strukturen helfen soll (Abb. 16).

Für jede Datenstruktur wurde mindestens eine TypeScript-Implementierung vorgestellt (diese stehen auch auf GitHub unter [2] zur Verfügung). Das zeigt, dass auch fortgeschrittene Datenstrukturen für Webentwickler keineswegs unerreichbar sind. Wie immer gilt: Die Art und Weise, wie Sie Ihre Daten verwenden möchten, ist der wichtigste Faktor bei der Wahl ihrer Repräsentation. Dazu gehören insbesondere:

• die verwendeten Algorithmen

• die Skalierung der Anwendung

• die typischen Nutzungsmuster

Scheuen Sie sich nicht, verschiedene Ansätze auszuprobieren, wenn Sie mit komplexen Daten arbeiten. Oft kann die richtige Datenstruktur den Code erheblich vereinfachen und gleichzeitig die Performance deutlich verbessern.